﻿//https://leetcode.cn/problems/longest-valid-parentheses/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int longestValidParentheses(string s)
    {
        int n = s.size();
        vector<int> dp(n);
        int ret = 0;

        for (int i = 1; i < n; i++)
        {
            if (s[i] == ')')
            {
                //当此时有一个完整的括号对 向前跳两步判断i-2位置有几个括号对
                if (s[i - 1] == '(')
                {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                //如果是两个连续的右括号 判断跳过前一个右括号（对）后存在的第一个左括号
                else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')
                {
                    //加上跳过的右括号（对）的最长子串
                    //如果越界 说明前面没有左括号与之匹配 只能+0
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                ret = max(ret, dp[i]);
            }

        }

        return ret;

    }
};